{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "1327bf22",
   "metadata": {},
   "source": [
    "[45. 跳跃游戏 II - 力扣（LeetCode）](https://leetcode.cn/problems/jump-game-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "d8b5d0dd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## 动态规划\n",
    "# 建立状态数组，存储当前位置到最后一位的步数\n",
    "# 从上往下，以此更新状态数组\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def jump(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n<2:\n",
    "            return 0\n",
    "        state = [0]*n\n",
    "        state[n-2] = 1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            num = nums[i]\n",
    "            if num+i>=n-1:\n",
    "                state[i]=1\n",
    "            else:\n",
    "                step = float('inf')\n",
    "                for j in range(1,num+1):\n",
    "                    step = min(step,1+state[i+j])\n",
    "                state[i] = step\n",
    "        return state[0]\n",
    "    \n",
    "nums = [2,3,0,1,4]\n",
    "solv = Solution()\n",
    "solv.jump(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b0434c03",
   "metadata": {},
   "source": [
    "[46. 全排列 - 力扣（LeetCode）](https://leetcode.cn/problems/permutations/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "0072c267",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 3, 4], [1, 4, 3], [3, 1, 4], [3, 4, 1], [4, 3, 1], [4, 1, 3]]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 无重复，\n",
    "# 按照位置逐步确定，位置1，有n个选择，位置2有n-1个，以此类推\n",
    "#\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "\n",
    "        def fun(k, nums):\n",
    "            if k==n:\n",
    "                nonlocal res\n",
    "                res.append(nums[:])\n",
    "\n",
    "            for i in range(k,n):\n",
    "                nums[i],nums[k] = nums[k],nums[i]\n",
    "                fun(k+1,nums)\n",
    "                nums[i],nums[k] = nums[k],nums[i]\n",
    "        \n",
    "        fun(0,nums)\n",
    "        return res\n",
    "nums = [1,3,4]\n",
    "solv = Solution()\n",
    "solv.permute(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "55320fc1",
   "metadata": {},
   "source": [
    "[47. 全排列 II - 力扣（LeetCode）](https://leetcode.cn/problems/permutations-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "9a3c8f8a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 1, 3, 4],\n",
       " [1, 1, 4, 3],\n",
       " [1, 3, 1, 4],\n",
       " [1, 3, 4, 1],\n",
       " [1, 4, 3, 1],\n",
       " [1, 4, 1, 3],\n",
       " [3, 1, 1, 4],\n",
       " [3, 1, 4, 1],\n",
       " [3, 4, 1, 1],\n",
       " [4, 1, 3, 1],\n",
       " [4, 1, 1, 3],\n",
       " [4, 3, 1, 1]]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## 有重复元素\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def permuteUnique(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "\n",
    "        def fun(nums, k):\n",
    "            if k==n:\n",
    "                nonlocal res\n",
    "                if nums not in res:\n",
    "                    res.append(nums[:])\n",
    "            \n",
    "            for i in range(k,n):\n",
    "                nums[i], nums[k] = nums[k],nums[i]\n",
    "                fun(nums,k+1)\n",
    "                nums[i], nums[k] = nums[k],nums[i]\n",
    "\n",
    "            \n",
    "        fun(nums,0)\n",
    "        return res\n",
    "    \n",
    "nums = [1,1,3,4]\n",
    "solv = Solution()\n",
    "solv.permuteUnique(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "32ec6faf",
   "metadata": {},
   "source": [
    "[48. 旋转图像 - 力扣（LeetCode）](https://leetcode.cn/problems/rotate-image/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "b089808c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[7, 4, 1]\n",
      "[8, 5, 2]\n",
      "[9, 6, 3]\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "class Solution:\n",
    "    def rotate(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        # 先上下翻转\n",
    "        for i in range(n//2):\n",
    "            matrix[i],matrix[n-1-i] = matrix[n-1-i],matrix[i]\n",
    "        \n",
    "        # 再对角翻转\n",
    "        for i in range(n):\n",
    "            for j in range(i,n): # 只需要处理上对角线\n",
    "                if i==j:\n",
    "                    continue\n",
    "                else:\n",
    "                    matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]\n",
    "\n",
    "        return matrix\n",
    "matrix = [[1,2,3],[4,5,6],[7,8,9]]\n",
    "solv = Solution()\n",
    "reMat = solv.rotate(matrix)\n",
    "for row in reMat:\n",
    "    print(row)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "887d5665",
   "metadata": {},
   "source": [
    "[49. 字母异位词分组 - 力扣（LeetCode）](https://leetcode.cn/problems/group-anagrams/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "e02f658c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]\n"
     ]
    }
   ],
   "source": [
    "# 哈希算法，构建字典\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]: \n",
    "        from collections import defaultdict\n",
    "        resDict = defaultdict(list)\n",
    "        for s in strs:\n",
    "            key = list(s)  # hash map\n",
    "            key.sort()\n",
    "            key = ''.join(key)\n",
    "            resDict[key].append(s)\n",
    "        res = list(resDict.values())\n",
    "        return res\n",
    "\n",
    "strs = [\"eat\", \"tea\", \"tan\", \"ate\", \"nat\", \"bat\"]\n",
    "solv = Solution()\n",
    "print(solv.groupAnagrams(strs))\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1955b648",
   "metadata": {},
   "source": [
    "[50. Pow(x, n) - 力扣（LeetCode）](https://leetcode.cn/problems/powx-n/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "0ade8261",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1024.0\n"
     ]
    }
   ],
   "source": [
    "## 快速幂乘\n",
    "# 以平方为单位，逐步乘，x->x^2-x^4->x^8--->x^9\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "\n",
    "        def quickMul(n):\n",
    "            if n==0:\n",
    "                return 1.0\n",
    "            y = quickMul(n//2)\n",
    "            if n%2==0:\n",
    "                return y*y\n",
    "            else:\n",
    "                return y*y*x\n",
    "        \n",
    "\n",
    "        m = 1.0\n",
    "        if n>=0:\n",
    "            res = quickMul(n)\n",
    "        else:\n",
    "            res = 1/quickMul(-n)\n",
    "        return res\n",
    "\n",
    "x,n = 2.0,10\n",
    "solv = Solution()\n",
    "print(solv.myPow(x,n))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb4ff2c3",
   "metadata": {},
   "source": [
    "[51. N 皇后 - 力扣（LeetCode）](https://leetcode.cn/problems/n-queens/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "9dff054e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ".Q..\n",
      "...Q\n",
      "Q...\n",
      "..Q.\n",
      "\n",
      "..Q.\n",
      "Q...\n",
      "...Q\n",
      ".Q..\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# 使用回溯的方法解决，\n",
    "# 难点主要在如何记录斜边上同一行的状态\n",
    "# 斜率正的斜边，同一斜边的点，行标+列表 的值相等\n",
    "# 斜率负的斜边，同一斜边的点， 行标-列标 的值相等\n",
    "# 列直接使用列标\n",
    "\n",
    "from typing import List\n",
    "from copy import deepcopy\n",
    "\n",
    "class Solution:\n",
    "    def solveNQueens(self, n: int) -> List[List[str]]:\n",
    "        columns = [0]*n\n",
    "        diag1 = [] # sum\n",
    "        diag2 = [] # diff\n",
    "        board = [['.']*n for _ in range(n)]\n",
    "        \n",
    "        res = []\n",
    "        \n",
    "        def backTrack(irow, columns, diag1, diag2, board):\n",
    "            # stop condition\n",
    "            if irow == n:\n",
    "                nonlocal res\n",
    "                res.append(deepcopy(board))\n",
    "                return\n",
    "            for icol in range(n):\n",
    "                if columns[icol]==1:\n",
    "                    continue\n",
    "                if irow+icol in diag1:\n",
    "                    continue\n",
    "                if irow-icol in diag2:\n",
    "                    continue\n",
    "                board[irow][icol] = 'Q'\n",
    "                columns[icol] = 1\n",
    "                diag1.append(irow+icol)\n",
    "                diag2.append(irow-icol)\n",
    "                \n",
    "                backTrack(irow+1, columns, diag1, diag2, board)\n",
    "                \n",
    "                board[irow][icol] = '.'\n",
    "                columns[icol] = 0\n",
    "                diag1.pop(-1)\n",
    "                diag2.pop(-1)\n",
    "        \n",
    "        backTrack(0,columns,diag1,diag2,board)\n",
    "        \n",
    "        for i in range(len(res)):\n",
    "            bd = res[i]\n",
    "            for iirow in range(len(bd)):\n",
    "                bd[iirow] = ''.join(bd[iirow])\n",
    "        \n",
    "        return res\n",
    "    \n",
    "n=4\n",
    "solv = Solution()\n",
    "res=solv.solveNQueens(n)\n",
    "\n",
    "for bd in res:\n",
    "    for row in bd:\n",
    "        print(row)\n",
    "    \n",
    "    print()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e4b7554",
   "metadata": {},
   "source": [
    "[52. N皇后 II - 力扣（LeetCode）](https://leetcode.cn/problems/n-queens-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "701520e8",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 相当于 ##51 的简化版\n",
    "class Solution:\n",
    "    def totalNQueens(self, n: int) -> int:\n",
    "        columns = [0]*n \n",
    "        diag1 = []\n",
    "        diag2 = []\n",
    "        res = 0\n",
    "\n",
    "        def backTrack(irow, columns, diag1, diag2):\n",
    "            if irow==n:\n",
    "                nonlocal res\n",
    "                res += 1\n",
    "            for icol in range(n):\n",
    "                if columns[icol] == 1:\n",
    "                    continue\n",
    "                if irow+icol in diag1:\n",
    "                    continue\n",
    "                if irow-icol in diag2:\n",
    "                    continue\n",
    "                \n",
    "                columns[icol] = 1\n",
    "                diag1.append(irow+icol)\n",
    "                diag2.append(irow-icol)\n",
    "\n",
    "                backTrack(irow+1,columns,diag1,diag2)\n",
    "\n",
    "                columns[icol] = 0\n",
    "                diag1.pop(-1)\n",
    "                diag2.pop(-1)\n",
    "            \n",
    "        backTrack(0,columns,diag1,diag2)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38d4e86c",
   "metadata": {},
   "source": [
    "[53. 最大子数组和 - 力扣（LeetCode）](https://leetcode.cn/problems/maximum-subarray/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "8f78f44b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        from copy import deepcopy\n",
    "        # 对列表累加求和，当和小于0的时候重新开始计数\n",
    "        # 对于和最大的序列，任意一个位置前面的序列和都应大于等于0\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        maxsum = nums[0]\n",
    "        if n<2:\n",
    "            return nums[0]\n",
    "        sumN = 0\n",
    "        for num in nums:\n",
    "            if sumN<0:\n",
    "                sumN = num\n",
    "            else:\n",
    "                sumN += num\n",
    "            maxsum = max(maxsum,sumN)\n",
    "        \n",
    "        return maxsum\n",
    "\n",
    "nums = [-2,1,-3,4,-1,2,1,-5,4] \n",
    "solv = Solution()\n",
    "print(solv.maxSubArray(nums))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5bd5fc88",
   "metadata": {},
   "source": [
    "[54. 螺旋矩阵 - 力扣（LeetCode）](https://leetcode.cn/problems/spiral-matrix/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "7b6dee6c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]\n"
     ]
    }
   ],
   "source": [
    "# 解题思路在于前路不通，就转向\n",
    "# 转向的顺序固定：右，下，左，上，并且循环\n",
    "# 使用一个同size的矩阵记录经过状态\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        state = [[0]*n for _ in range(m)]\n",
    "\n",
    "        # 右，下，左，上\n",
    "        DIRECTS = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        res = []\n",
    "        \n",
    "        def forward(ki,kj,matrix, state,Dindx):\n",
    "            \n",
    "            if (ki>m-1 or ki<0) or (kj>n-1 or kj<0) or (state[ki][kj]==1):\n",
    "                return\n",
    "            \n",
    "            nonlocal res\n",
    "            res.append(matrix[ki][kj])\n",
    "            state[ki][kj] =1\n",
    "            nonlocal DIRECTS\n",
    "            direct = DIRECTS[Dindx]\n",
    "\n",
    "            ki2 = ki+DIRECTS[Dindx][0]\n",
    "            kj2 = kj+DIRECTS[Dindx][1]\n",
    "\n",
    "            if (ki2>m-1 or ki2<0) or (kj2>n-1 or kj2<0):\n",
    "                Dindx = (Dindx+1)%4\n",
    "            elif (state[ki2][kj2]==1):\n",
    "                Dindx = (Dindx+1)%4\n",
    "\n",
    "            forward(ki+DIRECTS[Dindx][0],kj+DIRECTS[Dindx][1],matrix,state, Dindx)\n",
    "\n",
    "        forward(0,0,matrix,state,0)\n",
    "        return res\n",
    "\n",
    "matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]\n",
    "solve = Solution()\n",
    "print(solve.spiralOrder(matrix))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c11826e",
   "metadata": {},
   "source": [
    "[55. 跳跃游戏 - 力扣（LeetCode）](https://leetcode.cn/problems/jump-game/submissions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "a17caf0b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "## 使用动态规划的思想\n",
    "# 从后向前依次更新状态\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        state = [0]*n\n",
    "        state[n-1] = 1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            item = nums[i]\n",
    "            for j in range(1,min(item+1,n-i)):\n",
    "                if state[j+i] == 1:\n",
    "                    state[i] = 1\n",
    "                    break\n",
    "        \n",
    "        return state[0]==1\n",
    "\n",
    "if __name__=='__main__':\n",
    "    nums = [2,3,1,1,4]\n",
    "    solv = Solution()\n",
    "    print(solv.canJump(nums))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd9719ca",
   "metadata": {},
   "source": [
    "[56. 合并区间 - 力扣（LeetCode）](https://leetcode.cn/problems/merge-intervals/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "888befc2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 4], [5, 6], [7, 7], [8, 9], [11, 13]]\n"
     ]
    }
   ],
   "source": [
    "## 构建长数组，标记区间状态\n",
    "# 注意：题目是合并后无重叠，[1,3],[4,5] 无重叠；独自空间[1,3] [4,4] [5,6] 无重叠\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "from copy import deepcopy\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        re = [0]*2\n",
    "\n",
    "        # state list\n",
    "        # 0: null\n",
    "        # 1: fill\n",
    "        # 's\": start\n",
    "        # 'e': end\n",
    "        # 'sg': single\n",
    "        \n",
    "\n",
    "        # find maxValue\n",
    "        maxV = 0\n",
    "        for Lst in intervals:\n",
    "            maxV = max(maxV,max(Lst))\n",
    "        #\n",
    "\n",
    "        longLst = [0]*(maxV+7)\n",
    "        # code: 2: start, 3: end; 1:in, -1:outline\n",
    "        for l in intervals:\n",
    "            if l[0] == l[1]:\n",
    "                if longLst[l[0]]==0: # 单独空间[5,5],[0,0]\n",
    "                    longLst[l[0]] = 'sg'\n",
    "                continue\n",
    "            # set start\n",
    "            if longLst[l[0]]!=1:\n",
    "                if longLst[l[0]] == 'e':\n",
    "                    longLst[l[0]] = 1\n",
    "                else:\n",
    "                    longLst[l[0]] = 's'\n",
    "            # set end\n",
    "            if longLst[l[1]] !=1:\n",
    "                if longLst[l[1]]=='s':\n",
    "                    longLst[l[1]] = 1\n",
    "                else:\n",
    "                    longLst[l[1]] = 'e'          \n",
    "            # fit\n",
    "            for i in range(l[0]+1,l[1]):\n",
    "                longLst[i] = 1\n",
    "        \n",
    "        # get\n",
    "        for i in range(len(longLst)-1):\n",
    "            # find special\n",
    "            if longLst[i]=='sg':\n",
    "                res.append([i,i])\n",
    "\n",
    "            # find start\n",
    "            if longLst[i] == 's':\n",
    "                re[0] = i\n",
    "            if longLst[i]== 'e':\n",
    "                re[1] = i\n",
    "                res.append(deepcopy(re))\n",
    "                \n",
    "        return res\n",
    "    \n",
    "\n",
    "if __name__=='__main__':\n",
    "    intervals = [[5,6],[1,4],[6,6],[7,7],[11,13],[8,9]]\n",
    "    solv = Solution()\n",
    "    print(solv.merge(intervals))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3696d7c2",
   "metadata": {},
   "source": [
    "[57. 插入区间 - 力扣（LeetCode）](https://leetcode.cn/problems/insert-interval/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "3425689c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 2], [3, 10], [12, 16]]\n"
     ]
    }
   ],
   "source": [
    "## 模型分三段，前缀，相交段，后缀\n",
    "## 先找边界点，左： 右端点小于目标左端点， 右：左端点大于目标右端点\n",
    "# 前后缀：不做改变\n",
    "# 相交段：左端点取最小，右端点取最大\n",
    "# 注意处理：注意没有后缀，以及有后缀的情况插入的方式不一样\n",
    "# 注意：原区间为空\n",
    "\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:\n",
    "        left, right = newInterval\n",
    "        res = []\n",
    "        newleft,newright = left, right\n",
    "\n",
    "        from copy import deepcopy\n",
    "        if len(intervals)==0:\n",
    "            res.append(newInteral)\n",
    "            return res\n",
    "        flag = True\n",
    "        for interv in intervals:\n",
    "            if interv[1]<left:\n",
    "                res.append(deepcopy(interv))\n",
    "                continue\n",
    "\n",
    "            if interv[0]<=right:\n",
    "                newleft = min(newleft,interv[0]) # start\n",
    "                newright = max(newright,interv[1]) # end\n",
    "            else:\n",
    "                if flag:\n",
    "                    res.append([newleft,newright])\n",
    "                    flag = False\n",
    "                res.append(deepcopy(interv))\n",
    "        if flag:\n",
    "            res.append([newleft,newright])\n",
    "            flag = False\n",
    "        return res\n",
    "\n",
    "if __name__=='__main__':\n",
    "    intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]#[[1,3],[6,9]]\n",
    "    newInteral = [4,8]#[2,5]\n",
    "    solv = Solution()\n",
    "    print(solv.insert(intervals,newInteral))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c5a365b2",
   "metadata": {},
   "source": [
    "[58. 最后一个单词的长度 - 力扣（LeetCode）](https://leetcode.cn/problems/length-of-last-word/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "a2d11946",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "## \n",
    "class Solution:\n",
    "    def lengthOfLastWord(self, s: str) -> int:\n",
    "        Lst = list(s.strip().split())\n",
    "        return len(Lst[-1])\n",
    "s= 'hello word'\n",
    "solv = Solution()\n",
    "print(solv.lengthOfLastWord(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2cf0eabd",
   "metadata": {},
   "source": [
    "[59. 螺旋矩阵 II - 力扣（LeetCode）](https://leetcode.cn/problems/spiral-matrix-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a122e444",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 旋转矩阵的四个方向(0,1)->(1,0)->(0,-1)->(-1,0)\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        steps = [(0,1),(1,0),(0,-1),(-1,0)]\n",
    "        state = [[0]*n for _ in range(n)]\n",
    "        mat = [[0]*n for _ in range(n)]\n",
    "\n",
    "        irow,icol = 0, 0\n",
    "        val = 1\n",
    "        pos = 0\n",
    "        while val<=n**2:\n",
    "            mat[irow][icol] = val\n",
    "            val += 1\n",
    "            state[irow][icol] = 1\n",
    "\n",
    "            irow_next = irow + steps[pos][0]\n",
    "            icol_next = icol+ steps[pos][1]\n",
    "            if irow_next<0 or irow_next>=n or icol_next<0 or icol_next>=n or state[irow_next][icol_next]==1:\n",
    "                pos = (pos+1)%4\n",
    "\n",
    "            irow += steps[pos][0]\n",
    "            icol += steps[pos][1]\n",
    "\n",
    "        return mat \n",
    "\n",
    "if __name__=='__main__':\n",
    "    n = 5\n",
    "    solv = Solution()\n",
    "    print(solv.generateMatrix(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6fafd6b",
   "metadata": {},
   "source": [
    "[60. 排列序列 - 力扣（LeetCode）](https://leetcode.cn/problems/permutation-sequence/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "9c27414e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "321\n"
     ]
    }
   ],
   "source": [
    "## 数学推导法，自己没做出来\n",
    "# 按照顺序，使用数学推导，逐步推导出每一个元素\n",
    "# coding=utf-8\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        # 数学推断\n",
    "        # 求阶乘\n",
    "        factorial = [1]\n",
    "        for i in range(1,n):\n",
    "            factorial.append(factorial[-1]*i)\n",
    "        \n",
    "        k -= 1\n",
    "        ans = []\n",
    "        valid = [1]*(n+1)\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            order = k//factorial[n-i]+1 # 计算第i个位置的数值\n",
    "            for j in range(1,n+1): # 从目前剩余的数字中，挑选第order个（升序），并且改变这位的状态\n",
    "                order -= valid[j]\n",
    "                if order==0:\n",
    "                    ans.append(str(j))\n",
    "                    valid[j] = 0\n",
    "                    break\n",
    "            k %= factorial[n-i] # 更新k，推理下一个数字\n",
    "        return ''.join(ans)\n",
    "\n",
    "\n",
    "\n",
    "if __name__=='__main__':\n",
    "    n = 3\n",
    "    k = 6\n",
    "    solv = Solution()\n",
    "    print(solv.getPermutation(n,k))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d21bbf21",
   "metadata": {},
   "source": [
    "[61. 旋转链表 - 力扣（LeetCode）](https://leetcode.cn/problems/rotate-list/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "d2e27368",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 4 5 6 1 2 "
     ]
    }
   ],
   "source": [
    "## 计算链表的长度，然后从第n-k处截断，拼接到前面\n",
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:\n",
    "        h2 = ListNode(None)\n",
    "        length = 0\n",
    "\n",
    "        # 获取长度\n",
    "        pos = head\n",
    "        while pos:\n",
    "            length += 1\n",
    "            pos = pos.next\n",
    "        if length==0 or k==0: # 边界条件\n",
    "            return head\n",
    "        k = k%length\n",
    "        if k==0:  # 边界条件\n",
    "            return head\n",
    "\n",
    "        count = 0\n",
    "        pos = head\n",
    "        ## 去尾\n",
    "        while pos:\n",
    "            count += 1\n",
    "            if count ==length-k:\n",
    "                h2 = pos.next\n",
    "                pos.next = None\n",
    "                break\n",
    "            pos = pos.next\n",
    "        ## 增头\n",
    "        pos = head\n",
    "        pos2 = h2\n",
    "        # 找到尾部\n",
    "        while pos2.next:\n",
    "            pos2 = pos2.next\n",
    "        # 把第一个列表接到该链表后面\n",
    "        pos2.next = head\n",
    "\n",
    "        return h2\n",
    "\n",
    "\n",
    "if __name__=='__main__':\n",
    "    nums = [1,2,3,4,5,6]\n",
    "    k=4\n",
    "    head = ListNode(None)\n",
    "    pos = head\n",
    "    for num in nums:\n",
    "        pos.next = ListNode(num)\n",
    "        pos = pos.next\n",
    "    head = head.next\n",
    "\n",
    "    solv = Solution()\n",
    "    newhead = solv.rotateRight(head,k)\n",
    "    while newhead:\n",
    "        print(newhead.val,end=' ')\n",
    "        newhead = newhead.next"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16eb264b",
   "metadata": {},
   "source": [
    "[62. 不同路径 - 力扣（LeetCode）](https://leetcode.cn/problems/unique-paths/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "3ccdab10",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "28\n"
     ]
    }
   ],
   "source": [
    "## 动态规划\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        state = [[0]*n for _ in range(m)]\n",
    "        state[m-1][n-1] = 1\n",
    "        state[0][0] = 1\n",
    "\n",
    "        # ini\n",
    "        for i in range(m-1,-1,-1):\n",
    "            state[i][n-1] = 1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            state[m-1][i] = 1\n",
    "\n",
    "        if m>1 and n>1:\n",
    "            # update\n",
    "            for irow in range(m-2,-1,-1):\n",
    "                for icol in range(n-2,-1,-1):\n",
    "                    state[irow][icol] = state[irow+1][icol]+state[irow][icol+1]\n",
    "\n",
    "        return state[0][0]\n",
    "\n",
    "if __name__=='__main__':\n",
    "    m,n = 3,7\n",
    "    solv = Solution()\n",
    "    print(solv.uniquePaths(m,n))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86c158fa",
   "metadata": {},
   "source": [
    "[63. 不同路径 II - 力扣（LeetCode）](https://leetcode.cn/problems/unique-paths-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "b1021fb7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "## 动态规划\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        from copy import deepcopy\n",
    "\n",
    "        \n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "        state = [[0]*n for _ in range(m)]\n",
    "        \n",
    "        # init state\n",
    "        if obstacleGrid[m-1][n-1] == 1:\n",
    "            return 0\n",
    "        else: \n",
    "            state[m-1][n-1] = 1\n",
    "\n",
    "        for i in range(m-2,-1,-1):\n",
    "            if obstacleGrid[i][n-1] == 0:\n",
    "                state[i][n-1] = state[i+1][n-1]\n",
    "            else:\n",
    "                state[i][n-1] = 0\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if obstacleGrid[m-1][i] == 0:\n",
    "                state[m-1][i] = state[m-1][i+1]\n",
    "            else:\n",
    "                state[m-1][i]  = 0\n",
    "        \n",
    "        if m>1 and n>1:\n",
    "            # update\n",
    "            for irow in range(m-2,-1,-1):\n",
    "                for icol in range(n-2,-1,-1):\n",
    "                    if obstacleGrid[irow][icol] == 1:\n",
    "                        state[irow][icol] = 0\n",
    "                    else:\n",
    "                        state[irow][icol] = state[irow+1][icol]+state[irow][icol+1]\n",
    "        \n",
    "        return state[0][0]\n",
    "        \n",
    "if __name__=='__main__':\n",
    "    obst = [[0,0,0],[0,1,0],[0,0,0]]\n",
    "    solv = Solution()\n",
    "    print(solv.uniquePathsWithObstacles(obst))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6e8d375",
   "metadata": {},
   "source": [
    "[64. 最小路径和 - 力扣（LeetCode）](https://leetcode.cn/problems/minimum-path-sum/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "62559673",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 动态规划\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minPathSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        state = [[0]*n for _ in range(m)]\n",
    "        # initial\n",
    "        state[m-1][n-1] = grid[m-1][n-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            state[m-1][i] = grid[m-1][i]+state[m-1][i+1]\n",
    "        for i in range(m-2,-1,-1):\n",
    "            state[i][n-1] = grid[i][n-1] + state[i+1][n-1]\n",
    "\n",
    "        if n>1 and m>1:\n",
    "            # update\n",
    "            for irow in range(m-2,-1,-1):\n",
    "                for icol in range(n-2,-1,-1):\n",
    "                    tmp = grid[irow][icol]\n",
    "                    state[irow][icol] = min(state[irow+1][icol]+tmp, state[irow][icol+1]+tmp) \n",
    "\n",
    "        return state[0][0]   \n",
    "\n",
    "if __name__=='__main__':\n",
    "    grid = [[1,2,3],[4,5,6]]\n",
    "    solv = Solution()\n",
    "    print(solv.minPathSum(grid))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d17a20c6",
   "metadata": {},
   "source": [
    "[65. 有效数字 - 力扣（LeetCode）](https://leetcode.cn/problems/valid-number/)\n",
    "\\************ *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "8d89db11",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "## 有限状态自动机\n",
    "# 绘制状态转移表\n",
    "# 安装状态转移表构建构建状态转移函数\n",
    "# 根据状态转移函数处理字符串\n",
    "# 判断最后状态是否为合法的结束状态\n",
    "\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "from enum import Enum\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isNumber(self, s: str) -> bool:\n",
    "        # build state\n",
    "        State = Enum('State',['STATE_INITIAL', \\\n",
    "            'STATE_INT_SIGN', \n",
    "            'STATE_INTEGER',\n",
    "            'STATE_POINT',\n",
    "            'STATE_POINT_WITHOUT_INT',\n",
    "            'STATE_FRACTION',\n",
    "            'STATE_EXP',\n",
    "            'STATE_EXP_SIGN',\n",
    "            'STATE_EXP_NUMBER',\n",
    "            'STATE_END'])\n",
    "\n",
    "        CharType = Enum('CharType',['CHAR_NUMBER', \\\n",
    "            'CHAR_EXP',\n",
    "            'CHAR_POINT',\n",
    "            'CHAR_SIGN',\n",
    "            'CHAR_ILLEGAL'])\n",
    "\n",
    "        def toCharType(ch: str) -> CharType:\n",
    "            if ch.isdigit():\n",
    "                return CharType.CHAR_NUMBER\n",
    "            elif ch.lower() == 'e':\n",
    "                return CharType.CHAR_EXP\n",
    "            elif ch == '.':\n",
    "                return CharType.CHAR_POINT\n",
    "            elif ch == '+' or ch == '-':\n",
    "                return CharType.CHAR_SIGN\n",
    "            else:\n",
    "                return CharType.CHAR_ILLEGAL \n",
    "\n",
    "        # 状态转移\n",
    "        transfer = {\n",
    "            State.STATE_INITIAL:{\n",
    "                CharType.CHAR_NUMBER: State.STATE_INTEGER,\n",
    "                CharType.CHAR_POINT: State.STATE_POINT_WITHOUT_INT,\n",
    "                CharType.CHAR_SIGN: State.STATE_INT_SIGN\n",
    "            },\n",
    "            State.STATE_INT_SIGN:{\n",
    "                CharType.CHAR_NUMBER: State.STATE_INTEGER,\n",
    "                CharType.CHAR_POINT: State.STATE_POINT_WITHOUT_INT\n",
    "            },\n",
    "            State.STATE_INTEGER:{\n",
    "                CharType.CHAR_NUMBER: State.STATE_INTEGER,\n",
    "                CharType.CHAR_POINT: State.STATE_POINT,\n",
    "                CharType.CHAR_EXP: State.STATE_EXP\n",
    "            },\n",
    "            State.STATE_POINT:{\n",
    "                CharType.CHAR_NUMBER: State.STATE_FRACTION,\n",
    "                CharType.CHAR_EXP: State.STATE_EXP\n",
    "            },\n",
    "            State.STATE_POINT_WITHOUT_INT:{\n",
    "                CharType.CHAR_NUMBER: State.STATE_FRACTION,\n",
    "            },\n",
    "            State.STATE_FRACTION:{\n",
    "                CharType.CHAR_NUMBER: State.STATE_FRACTION,\n",
    "                CharType.CHAR_EXP: State.STATE_EXP,\n",
    "            },\n",
    "            State.STATE_EXP:{\n",
    "                CharType.CHAR_SIGN: State.STATE_EXP_SIGN,\n",
    "                CharType.CHAR_NUMBER: State.STATE_EXP_NUMBER\n",
    "            },\n",
    "            State.STATE_EXP_SIGN:{\n",
    "                CharType.CHAR_NUMBER: State.STATE_EXP_NUMBER\n",
    "            },\n",
    "            State.STATE_EXP_NUMBER:{\n",
    "                CharType.CHAR_NUMBER: State.STATE_EXP_NUMBER,\n",
    "            }\n",
    "        }\n",
    "\n",
    "        # update\n",
    "        st = State.STATE_INITIAL\n",
    "        for ch in s:\n",
    "            typ = toCharType(ch)\n",
    "            if typ not in transfer[st]:\n",
    "                return False\n",
    "            st = transfer[st][typ]\n",
    "        \n",
    "        return st in [State.STATE_INTEGER, State.STATE_POINT, State.STATE_FRACTION, State.STATE_EXP_NUMBER,State.STATE_END]\n",
    "\n",
    "\n",
    "if __name__=='__main__':\n",
    "    s = '-0.5e3'\n",
    "    solv=Solution()\n",
    "    print(solv.isNumber(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1ed643a",
   "metadata": {},
   "source": [
    "[66. 加一 - 力扣（LeetCode）](https://leetcode.cn/problems/plus-one/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e71d296e",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 模拟计算机的加法操作\n",
    "# coding=utf-8\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def plusOne(self, digits: List[int]) -> List[int]:\n",
    "        flag = 0\n",
    "        val = 1\n",
    "        for i in range(len(digits)-1,-1,-1):\n",
    "            sumTmp = (digits[i]+flag+val)%10\n",
    "            flag = (digits[i]+flag+val)//10\n",
    "            digits[i] = sumTmp\n",
    "            val = 0\n",
    "        if flag:\n",
    "            digits.insert(0,1)\n",
    "        return digits\n",
    "\n",
    "if __name__=='__main__':\n",
    "    digits = [9,9,9,9]\n",
    "    solv = Solution()\n",
    "    print(solv.plusOne(digits))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d55e61c",
   "metadata": {},
   "source": [
    "[67. 二进制求和 - 力扣（LeetCode）](https://leetcode.cn/problems/add-binary/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "d9446208",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def addBinary(self, a: str, b: str) -> str:\n",
    "        a = list(map(int,list(a)))\n",
    "        b = list(map(int,list(b)))\n",
    "        reSum = [0]*max(len(a),len(b))\n",
    "\n",
    "        ia,ib,pos = len(a)-1, len(b)-1,len(reSum)-1\n",
    "        flag = 0\n",
    "        while ia>=0 and ib>=0:\n",
    "            reSum[pos] = (a[ia]+b[ib]+flag)%2\n",
    "            flag = (a[ia]+b[ib]+flag)//2\n",
    "            ia -= 1\n",
    "            ib -= 1\n",
    "            pos -= 1\n",
    "        while ia>=0:\n",
    "            reSum[pos] = (a[ia]+flag)%2\n",
    "            flag = (a[ia]+flag)//2\n",
    "            ia -= 1\n",
    "            pos -= 1\n",
    "        while ib>=0:\n",
    "            reSum[pos] = (b[ib]+flag)%2\n",
    "            flag = (b[ib]+flag)//2\n",
    "            ib -= 1\n",
    "            pos -= 1\n",
    "        if flag:\n",
    "            reSum.insert(0,1)\n",
    "        return ''.join(map(str,reSum))\n",
    "        \n",
    "\n",
    "\n",
    "if __name__=='__main__':\n",
    "    a = '1'\n",
    "    b = '111'\n",
    "    solv = Solution()\n",
    "    print(solv.addBinary(a,b))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a49273b6",
   "metadata": {},
   "source": [
    "[68. 文本左右对齐 - 力扣（LeetCode）](https://leetcode.cn/problems/text-justification/)\n",
    "\n",
    "\\**********"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "47f895a3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "This    is    an 16\n",
      "example  of text 16\n",
      "justification.   16\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:\n",
    "        # 分为三种情况\n",
    "        # 1，当前行为最后一行，\n",
    "        # 2，当前行不是最后一行，而且当前行只有一个单词\n",
    "        # 3，当前行不是最后一行，而且当前行不止一个单词\n",
    "\n",
    "        # 首先确定当前行的单词个数\n",
    "        left,right =0,0 # 每行的左右边界\n",
    "        n = len(words)\n",
    "        res = []\n",
    "\n",
    "        while True:\n",
    "            left = right # 重置左端点\n",
    "            rowlen = 0\n",
    "            # 计算当前行的单词的长度\n",
    "            while right<=n-1 and rowlen+len(words[right])+(right-left)<=maxWidth:\n",
    "                rowlen += len(words[right])\n",
    "                right += 1\n",
    "            \n",
    "            # 如果为最后一行\n",
    "            if right==n: # 这一行可以包含最后一个单词\n",
    "                blanklength = maxWidth - rowlen - (right-1-left)\n",
    "                res.append(' '.join(words[left:right])+' '*blanklength)\n",
    "                return res\n",
    "            # 非最后一行，并且只包含一个单词\n",
    "            elif right-left == 1:\n",
    "                blanklength = maxWidth - len(words[left])\n",
    "                res.append(words[left]+' '*blanklength)\n",
    "            # 非最后一行，并且不止一个单词\n",
    "            else:\n",
    "                blanklength = maxWidth - rowlen\n",
    "                spacePerW = blanklength//(right-1-left)\n",
    "                spaceExtra = blanklength%(right-1-left)\n",
    "                tmp2 = ' '*spacePerW\n",
    "                if spaceExtra == 0: # 空格刚好均匀分布\n",
    "                    res.append(tmp2.join(words[left:right]))\n",
    "                else:\n",
    "                    tmp1 = ' '*(spacePerW+1)                                 \n",
    "                    s1 = tmp1.join(words[left:left+spaceExtra+1])\n",
    "                    s2 = tmp2.join(words[left+spaceExtra+1:right])\n",
    "                    res.append(s1+tmp2+s2)\n",
    "\n",
    "if __name__=='__main__':\n",
    "    words =  [\"This\", \"is\", \"an\", \"example\", \"of\", \"text\", \"justification.\"]\n",
    "    maxWidth = 16\n",
    "    solv = Solution()\n",
    "    res = solv.fullJustify(words,maxWidth)\n",
    "    for s in res:\n",
    "        print(s,end=' ')\n",
    "        print(len(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a0550b7",
   "metadata": {},
   "source": [
    "[69. x 的平方根 - 力扣（LeetCode）](https://leetcode.cn/problems/sqrtx/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "19444c53",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "## 二分法\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        left,right = 0,x\n",
    "        if x==0 or x==1:\n",
    "            return x\n",
    "        import math\n",
    "        # 二分法\n",
    "        while left<=right:\n",
    "            if (math.floor(left))**2<x and (math.floor(left)+1)**2>x:\n",
    "                return math.floor(left)\n",
    "                \n",
    "            mid = left+(right-left)/2.0\n",
    "            if mid**2==x:\n",
    "                return math.floor(mid)\n",
    "            elif mid**2<x:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "if __name__=='__main__':\n",
    "    x = 13\n",
    "    solv = Solution()\n",
    "    print(solv.mySqrt(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aea93c10",
   "metadata": {},
   "source": [
    "[70. 爬楼梯 - 力扣（LeetCode）](https://leetcode.cn/problems/climbing-stairs/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "b2300553",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "## 动态规划，能到当前阶梯的只有两个阶梯\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "## 爬楼梯\n",
    "class Solution:\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        state = [0]*(n+1)\n",
    "        state[0] = 1\n",
    "        state[1] = 1\n",
    "        \n",
    "        for i in range(2,n+1):\n",
    "            state[i] = state[i-1]+state[i-2]\n",
    "\n",
    "        return state[n]\n",
    "\n",
    "if __name__=='__main__':\n",
    "    solv = Solution()\n",
    "    print(solv.climbStairs(3))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "237f2718",
   "metadata": {},
   "source": [
    "[71. 简化路径 - 力扣（LeetCode）](https://leetcode.cn/problems/simplify-path/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "e5e5dd98",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "/c\n"
     ]
    }
   ],
   "source": [
    "## 使用栈的方法\n",
    "# 忽略 ‘.’,'' 空字符\n",
    "\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def simplifyPath(self, path: str) -> str:\n",
    "        ## 使用栈来操作\n",
    "        names = path.split('/')\n",
    "        stack = []\n",
    "        for name in names:\n",
    "            if name=='..':\n",
    "                if stack:\n",
    "                    stack.pop(-1)\n",
    "            elif name and name!='.': # 忽略 空字符串和‘.’\n",
    "                stack.append(name)\n",
    "        \n",
    "        return '/'+'/'.join(stack)\n",
    "\n",
    "if __name__=='__main__':\n",
    "    path = '/a/./b/../../c/'\n",
    "    solv = Solution()\n",
    "    print(solv.simplifyPath(path))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e21ad26",
   "metadata": {},
   "source": [
    "[72. 编辑距离 - 力扣（LeetCode）](https://leetcode.cn/problems/edit-distance/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "e5b40d4e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        ## 使用动态规划\n",
    "        # 定义状态：给定字符串，A，B， DP[i][j] 表示将字符串A[:i] 转变为B[:j]所需的最小操作数\n",
    "        # 三个动作会发生状态转移\n",
    "        # 1. 在A的末尾删除一个字母： DP[i-1][j]+1->DP[i][j]： 删除A[i]\n",
    "        # 2. 在A的末尾插入一个字母： DP[i][j-1]+1->DP[i][j],  插入B[j] 在A的末尾\n",
    "        # 3. 替换A的末尾字母： DP[i-1][j-1]+1->DP[i][j] or DP[i-1][j-1]->DP[i][j], 此时需要比较A[i],B[j],相同不用操作，否则替换A[i]为B[j]\n",
    "        # 绘制状态转移矩阵\n",
    "        n1, n2 = len(word1), len(word2)\n",
    "        state = [[0]*(n1+1) for _ in range(n2+1)]\n",
    "        # word1: column\n",
    "        # word2: row\n",
    "        # initial\n",
    "        state[0][0] = 0\n",
    "        for i in range(1, n1+1):\n",
    "            state[0][i] = i\n",
    "        for i in range(1, n2+1):\n",
    "            state[i][0] = i\n",
    "        # update\n",
    "        for irow in range(1,n2+1):\n",
    "            for icol in range(1,n1+1):\n",
    "                left = state[irow][icol-1]+1\n",
    "                up = state[irow-1][icol]+1\n",
    "                if word2[irow-1] == word1[icol-1]:\n",
    "                    left_up = state[irow-1][icol-1]\n",
    "                else:\n",
    "                    left_up = state[irow-1][icol-1]+1\n",
    "                state[irow][icol] = min(left,up, left_up)\n",
    "        \n",
    "        return state[-1][-1]\n",
    "\n",
    "if __name__=='__main__':\n",
    "    solv = Solution()\n",
    "    print(solv.minDistance('horse','rose'))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3db8551c",
   "metadata": {},
   "source": [
    "[73. 矩阵置零 - 力扣（LeetCode）](https://leetcode.cn/problems/set-matrix-zeroes/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "655c390b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before\n",
      "[0, 1, 2, 0]\n",
      "[3, 4, 5, 2]\n",
      "[1, 3, 1, 5]\n",
      "after\n",
      "[0, 0, 0, 0]\n",
      "[0, 4, 5, 0]\n",
      "[0, 3, 1, 0]\n"
     ]
    }
   ],
   "source": [
    "## 使用 矩阵的首行标记对应的行和列是否含有0\n",
    "# 注意 这样会改变首行首列，因此我们使用两个变量存储首行首列的状态\n",
    "# 置零的\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def setZeroes(self, matrix: List[List[int]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify matrix in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(matrix)\n",
    "        m = len(matrix[0])\n",
    "        row0 = None\n",
    "        col0 = None\n",
    "\n",
    "        # 把非首行首列的0状态放在对应的首行和首列\n",
    "        # foward\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if matrix[i][j] == 0:\n",
    "                    if i==0:   # 记录首行状态\n",
    "                        row0 = 's'\n",
    "                    if j==0:   # 记录首列状态\n",
    "                        col0 = 's'\n",
    "                    matrix[i][0] = 's'\n",
    "                    matrix[0][j] = 's'\n",
    "        # 处理非首行，首列\n",
    "        for i in range(1,n):\n",
    "            if matrix[i][0]=='s':\n",
    "                matrix[i][:] = [0]*m\n",
    "        for j in range(1,m):\n",
    "            if matrix[0][j] == 's':\n",
    "                for ii in range(n):\n",
    "                    matrix[ii][j] = 0\n",
    "        # 处理首行，首列\n",
    "        if row0=='s':\n",
    "            matrix[0][:] = [0]*m\n",
    "        if col0=='s':\n",
    "            for i in range(n):\n",
    "                matrix[i][0] = 0\n",
    "        \n",
    "if __name__=='__main__':\n",
    "    solv = Solution()\n",
    "    matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]\n",
    "    print('before')\n",
    "    for row in matrix:\n",
    "        print(row)\n",
    "\n",
    "    print('after')\n",
    "    solv.setZeroes(matrix)\n",
    "    for row in matrix:\n",
    "        print(row)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1066be60",
   "metadata": {},
   "source": [
    "[74. 搜索二维矩阵 - 力扣（LeetCode）](https://leetcode.cn/problems/search-a-2d-matrix/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "fe24c661",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "## 二分法抽查\n",
    "# 首先确定所在的行\n",
    "# 二分法注意更改边界的时候向左或向右偏移一位\n",
    "\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        n,m = len(matrix),len(matrix[0])\n",
    "        if target<matrix[0][0] or target>matrix[-1][-1]:\n",
    "            return False\n",
    "        # find target row\n",
    "        row = 0\n",
    "        for i in range(n):\n",
    "            if matrix[i][0]<=target and target<=matrix[i][m-1]:\n",
    "                row = i\n",
    "\n",
    "\n",
    "        # binary search\n",
    "        def binarySearch(left:int,right:int,row:int) ->bool:\n",
    "            while left<=right:\n",
    "                mid = left+((right-left)>>1)\n",
    "                if matrix[row][mid]==target:\n",
    "                    return True\n",
    "                elif matrix[row][mid]>target:\n",
    "                    right = mid-1\n",
    "                else:\n",
    "                    left = mid+1\n",
    "            return False\n",
    "        \n",
    "        return binarySearch(0,m-1,row)\n",
    "\n",
    "if __name__=='__main__':\n",
    "    solv = Solution()\n",
    "    matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]\n",
    "    target = 7\n",
    "    print(solv.searchMatrix(matrix, target))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73d07497",
   "metadata": {},
   "source": [
    "[75. 颜色分类 - 力扣（LeetCode）](https://leetcode.cn/problems/sort-colors/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "79469451",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 快速排序\n",
    "\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        def partation(left:int, right:int, nums:List[int])->int:\n",
    "            pivot = nums[right]\n",
    "            pos = left\n",
    "            i = left\n",
    "            while i<=right:\n",
    "                if nums[i]<pivot:\n",
    "                    nums[i],nums[pos] = nums[pos],nums[i]\n",
    "                    pos += 1\n",
    "                i += 1\n",
    "            nums[right],nums[pos] = nums[pos],nums[right]\n",
    "            return pos\n",
    "\n",
    "        def quickSort(left:int,right:int, nums:List)->None:\n",
    "            # stop\n",
    "            if left>=right:\n",
    "                return\n",
    "\n",
    "            q = partation(left, right, nums)\n",
    "            quickSort(left,q-1,nums)\n",
    "            quickSort(q+1, right,nums) \n",
    "\n",
    "        quickSort(0,len(nums)-1,nums)\n",
    "\n",
    "\n",
    "if __name__=='__main__':\n",
    "    solv = Solution()\n",
    "    nums = [2,0,2,1,1,0]\n",
    "    solv.sortColors(nums)\n",
    "    print(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d0d2207",
   "metadata": {},
   "source": [
    "[76. 最小覆盖子串 - 力扣（LeetCode）](https://leetcode.cn/problems/minimum-window-substring/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "0e1581f7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "BANC\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "\n",
    "        ## 左右指针滑动收缩\n",
    "        # 哈希表\n",
    "        from collections import defaultdict\n",
    "        from copy import deepcopy\n",
    "        Dict = defaultdict(int)\n",
    "        tLen = 0\n",
    "        for st in t:\n",
    "            Dict[st] += 1\n",
    "            tLen += 1\n",
    "        \n",
    "        minLeft,minRight = 0, len(s)-1\n",
    "\n",
    "        left = right = 0\n",
    "        # 找到右边界\n",
    "        flag = False # 没找到 合适的右端点 False\n",
    "        for right,ss in enumerate(s):\n",
    "            if Dict[ss] > 0:\n",
    "                tLen -= 1\n",
    "            Dict[ss] -= 1\n",
    "            if tLen==0:\n",
    "                flag = True\n",
    "                # 收缩左边界\n",
    "                while left<=right:\n",
    "                    if Dict[s[left]] ==0:\n",
    "                        if minRight-minLeft > right-left:\n",
    "                            minRight,minLeft = right, left # 保留最短\n",
    "                        break\n",
    "                    else:\n",
    "                        Dict[s[left]] += 1\n",
    "                    left += 1\n",
    "\n",
    "                tLen += 1\n",
    "                Dict[s[left]] += 1\n",
    "                left += 1 # 右移左端点，迫使右端点找下一个目标段\n",
    "                \n",
    "        # 没有找到合适的右端点\n",
    "        if not flag:\n",
    "            return ''\n",
    "        else:\n",
    "            return s[minLeft:minRight+1]\n",
    "\n",
    "\n",
    "if __name__=='__main__':\n",
    "    s = \"ADOBECODEBANC\"\n",
    "    t = \"ABC\"\n",
    "    solv = Solution()\n",
    "    print(solv.minWindow(s,t))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "877ff4d7",
   "metadata": {},
   "source": [
    "[77. 组合 - 力扣（LeetCode）](https://leetcode.cn/problems/combinations/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "59074757",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[4, 3], [4, 2], [4, 1], [3, 2], [3, 1], [2, 1]]\n"
     ]
    }
   ],
   "source": [
    "## 使用回溯算法\n",
    "\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "from copy import deepcopy\n",
    "\n",
    "class Solution:\n",
    "    def combine(self, n: int, k: int) -> List[List[int]]:\n",
    "        \n",
    "\n",
    "        Lst1 = list(range(1,n+1))\n",
    "        Lst2 = []\n",
    "        res = []\n",
    "\n",
    "        if n==k:\n",
    "            res.append(list(range(1,k+1)))\n",
    "            return res\n",
    "        # 回溯法解决\n",
    "        def backTrack(pos:int, res: List[int],Lst1: List[int], Lst2: List[int],k:int)->None:\n",
    "            if len(Lst2)>=k:\n",
    "                res.append(deepcopy(Lst2))\n",
    "                return\n",
    "            if pos<0:\n",
    "                return\n",
    "            \n",
    "            item = Lst1[pos]\n",
    "            Lst2.append(item)\n",
    "            backTrack(pos-1,res,Lst1,Lst2,k)\n",
    "            Lst2.pop(-1)\n",
    "            backTrack(pos-1,res,Lst1,Lst2,k)\n",
    "        \n",
    "        backTrack(n-1,res, Lst1, Lst2, k)\n",
    "        return res\n",
    "\n",
    "if __name__=='__main__':\n",
    "    solv = Solution()\n",
    "    print(solv.combine(4,2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc641ae1",
   "metadata": {},
   "source": [
    "[78. 子集 - 力扣（LeetCode）](https://leetcode.cn/problems/subsets/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "ccbcd4f6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[], [3], [3, 2], [3, 2, 1], [3, 1], [2], [2, 1], [1]]\n"
     ]
    }
   ],
   "source": [
    "## 回溯方法解决\n",
    "# 每次有新增的时候才添加到返回数组中\n",
    "# coding=utf-8\n",
    "from copy import deepcopy\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        res = [[]]\n",
    "\n",
    "        def backTrack(nums:List[int], pos:int, Lst:List[int])->None:\n",
    "               \n",
    "            if pos<0:\n",
    "                return\n",
    "\n",
    "            item = nums[pos]\n",
    "            Lst.append(item)\n",
    "            nonlocal res \n",
    "            res.append(deepcopy(Lst)) # 有新增的时候添加\n",
    "            backTrack(nums,pos-1,Lst)\n",
    "            Lst.pop(-1)\n",
    "            backTrack(nums,pos-1,Lst)\n",
    "\n",
    "        backTrack(nums,len(nums)-1,[])\n",
    "\n",
    "        return res\n",
    "\n",
    "if __name__=='__main__':\n",
    "    solv = Solution()\n",
    "    nums = [1,2,3]\n",
    "    print(solv.subsets(nums))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "20adc1c0",
   "metadata": {},
   "source": [
    "[79. 单词搜索 - 力扣（LeetCode）](https://leetcode.cn/problems/word-search/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "02e2d01e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "['A', 'A', 'A', 'A', 'A', 'A']\n",
      "['A', 'A', 'A', 'A', 'A', 'A']\n",
      "['A', 'A', 'A', 'A', 'A', 'A']\n",
      "['A', 'A', 'A', 'A', 'A', 'A']\n",
      "['A', 'A', 'A', 'A', 'A', 'A']\n",
      "['A', 'A', 'A', 'A', 'A', 'A']\n"
     ]
    }
   ],
   "source": [
    "## 使用回溯算法， 四个方向运动，\n",
    "# coding=utf-8\n",
    "from ctypes.wintypes import WORD\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        from copy import deepcopy\n",
    "        # 定义check(i,j,k)表示从board[i,j]开始是否能检测到word[k:]\n",
    "        n,m = len(board),len(board[0])\n",
    "        \n",
    "        def check(i:int,j:int,k:int,state:List[int])->None:\n",
    "            nonlocal n,m\n",
    "            if i<0 or i>n-1 or j<0 or j>m-1 or state[i][j]==1:\n",
    "                return False\n",
    "\n",
    "            if board[i][j] == word[k]:\n",
    "                state[i][j] = 1\n",
    "                if k == len(word)-1:\n",
    "                    return True\n",
    "                else:\n",
    "                    if check(i,j+1,k+1,state):\n",
    "                        return True\n",
    "                    if check(i,j-1,k+1,state):\n",
    "                        return True\n",
    "                    if check(i-1,j,k+1,state):\n",
    "                        return True\n",
    "                    if check(i+1,j,k+1,state):\n",
    "                        return True\n",
    "                state[i][j] = 0\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        state = [[0]*m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if check(i,j,0,state):\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "if __name__=='__main__':\n",
    "    solv = Solution()\n",
    "    board = [[\"A\",\"A\",\"A\",\"A\",\"A\",\"A\"],[\"A\",\"A\",\"A\",\"A\",\"A\",\"A\"],[\"A\",\"A\",\"A\",\"A\",\"A\",\"A\"],[\"A\",\"A\",\"A\",\"A\",\"A\",\"A\"],[\"A\",\"A\",\"A\",\"A\",\"A\",\"A\"],[\"A\",\"A\",\"A\",\"A\",\"A\",\"A\"]]\n",
    "    word = \"AAAAAAAAAAAAAAB\"\n",
    "    print(solv.exist(board,word))\n",
    "    for b in board:\n",
    "        print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10c79d68",
   "metadata": {},
   "source": [
    "[80. 删除有序数组中的重复项 II - 力扣（LeetCode）](https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "c8ec8f86",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "[1, 1, 2, 2, 3, 3]\n"
     ]
    }
   ],
   "source": [
    "## 遍历+数组原地删除\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicates(self, nums: List[int]) -> int:\n",
    "        win = [0]*3\n",
    "        n = len(nums)\n",
    "        left,right = 0,n-1\n",
    "        while left<=right-2:\n",
    "            win[:] = nums[left:left+3]\n",
    "            if win[0] == win[2]:\n",
    "                i = left+2\n",
    "                while i<= right-1:# 左移覆盖\n",
    "                    nums[i] = nums[i+1]\n",
    "                    i += 1\n",
    "                right -= 1\n",
    "                continue\n",
    "            else:\n",
    "                left += 1\n",
    "        return right+1\n",
    "\n",
    "if __name__=='__main__':\n",
    "    solv = Solution()\n",
    "    nums = [1,1,1,2,2,3]\n",
    "    print(solv.removeDuplicates(nums))\n",
    "    print(nums)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7c5dc0ef",
   "metadata": {},
   "source": [
    "[81. 搜索旋转排序数组 II - 力扣（LeetCode）](https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "2ae18826",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "## 二分法的变种： 搜索旋转数组\n",
    "# 先判定有序区间可以简化代码\n",
    "# 注意：当中值和左右端点相同的情况，无法判定有限区间时，两边同时搜索\n",
    "\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def search(self, nums: List[int], target: int) -> bool:\n",
    "        ## 二分法的变体：旋转数组的搜索\n",
    "        ## 先判定有序段\n",
    "\n",
    "        def binarySearch(left:int, right:int):\n",
    "            nonlocal nums, target\n",
    "            if left>right:\n",
    "                return False\n",
    "            \n",
    "            while left<=right:\n",
    "                mid = left+((right-left)>>1)\n",
    "                if nums[mid]==target:\n",
    "                    return True\n",
    "\n",
    "                if nums[mid]==nums[left]==nums[right]: # 无法判定左右谁是有序\n",
    "                    if binarySearch(left,mid-1) or binarySearch(mid+1,right):\n",
    "                        return True\n",
    "                if nums[mid]>=nums[left]: # 左侧为有序\n",
    "                    if nums[mid]>=target>= nums[left]: # 在左侧区间\n",
    "                        right = mid-1\n",
    "                    else: # 在右侧区间\n",
    "                        left = mid+1 \n",
    "                else: # 右侧为有序\n",
    "                    if nums[mid]<=target<=nums[right]: # 在右侧区间\n",
    "                        left = mid+1\n",
    "                    else: # 在左侧区间\n",
    "                        right = mid-1\n",
    "            return False\n",
    "            \n",
    "        return binarySearch(0,len(nums)-1)\n",
    "\n",
    "if __name__=='__main__':\n",
    "    solv = Solution()\n",
    "    nums = [1,0,1,1,1]\n",
    "    target = 0\n",
    "    print(solv.search(nums,target))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c7e8424f",
   "metadata": {},
   "source": [
    "[82. 删除排序链表中的重复元素 II - 力扣（LeetCode）](https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "94b51bed",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 5 "
     ]
    }
   ],
   "source": [
    "# 链表删除操作，记得删除第一个重复的元素\n",
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        # 删除重复节点\n",
    "        h1 = ListNode(None)\n",
    "        h1.next = head\n",
    "        \n",
    "        if head==None: # 空链表\n",
    "            return head\n",
    "\n",
    "        flag = False\n",
    "        reader = h1\n",
    "        while reader.next.next:\n",
    "            if reader.next.val==reader.next.next.val:\n",
    "                flag = True\n",
    "                reader.next = reader.next.next # 删除reader.next\n",
    "            else: # 后面的第一个 和第二个不同\n",
    "                if flag:\n",
    "                    reader.next = reader.next.next # 删除第一个重复元素\n",
    "                    flag = False\n",
    "                    continue\n",
    "                reader = reader.next\n",
    "        if flag:\n",
    "            reader.next = reader.next.next\n",
    "        return h1.next\n",
    "\n",
    "if __name__=='__main__':\n",
    "    nums = [1,2,3,3,4,4,5]\n",
    "    solv = Solution()\n",
    "    head = ListNode(None)\n",
    "    reader = head\n",
    "    for num in nums:\n",
    "        tmp = ListNode(num)\n",
    "        reader.next = tmp\n",
    "        reader = reader.next\n",
    "    head = head.next\n",
    "    newhead = solv.deleteDuplicates(head)\n",
    "    while newhead:\n",
    "        print(newhead.val,end=' ')\n",
    "        newhead = newhead.next"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d589bd1f",
   "metadata": {},
   "source": [
    "[83. 删除排序链表中的重复元素 - 力扣（LeetCode）](https://leetcode.cn/problems/remove-duplicates-from-sorted-list/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "e08ffe01",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 "
     ]
    }
   ],
   "source": [
    "## 上一题的简化版\n",
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "\n",
    "        h1 = ListNode(None)\n",
    "        h1.next = head\n",
    "        reader = h1\n",
    "\n",
    "        if not head:\n",
    "            return head\n",
    "\n",
    "        while reader.next.next:\n",
    "            if reader.next.val == reader.next.next.val:\n",
    "                reader.next = reader.next.next\n",
    "            else:\n",
    "                reader = reader.next\n",
    "        return h1.next\n",
    "\n",
    "if __name__=='__main__':\n",
    "    nums = [1,2,3,3,4,4,5]\n",
    "    solv = Solution()\n",
    "    head = ListNode(None)\n",
    "    reader = head\n",
    "    for num in nums:\n",
    "        tmp = ListNode(num)\n",
    "        reader.next = tmp\n",
    "        reader = reader.next\n",
    "    head = head.next\n",
    "    newhead = solv.deleteDuplicates(head)\n",
    "    while newhead:\n",
    "        print(newhead.val,end=' ')\n",
    "        newhead = newhead.next"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bedba787",
   "metadata": {},
   "source": [
    "[84. 柱状图中最大的矩形 - 力扣（LeetCode）](https://leetcode.cn/problems/largest-rectangle-in-histogram/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "009efbae",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 使用单调栈\n",
    "\n",
    "# coding=utf-8\n",
    "from subprocess import HIGH_PRIORITY_CLASS\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        ## 左右指针，收缩\n",
    "        # 遍历高度\n",
    "        # 以当前点作为参照点，向左向右找到高度小于该点的边界点，\n",
    "        # 左右边界中间的最大矩形面积=(r-l-1)*h\n",
    "        # 遍历所有点对应的最大矩形面积，取最大值就是所求\n",
    "        ## 使用使用两个单调栈分别找到每一个点的左右边界\n",
    "\n",
    "        n = len(heights)\n",
    "        left = [0]*n\n",
    "        right = [0]*n\n",
    "\n",
    "        # 使用一个递增的单调栈，找到所有点的左边界\n",
    "        mono_stack = []\n",
    "        for i in range(n):\n",
    "            while mono_stack and heights[mono_stack[-1]]>=heights[i]:\n",
    "                mono_stack.pop(-1)\n",
    "            left[i] = mono_stack[-1] if mono_stack else -1 # 记录当前高度的左端点\n",
    "            mono_stack.append(i)\n",
    "        \n",
    "        # 使用一个递增的单调栈，找到所有端点的右边界\n",
    "        mono_stack = []\n",
    "        for i in range(n-1,-1,-1): # 自右向左遍历\n",
    "            while mono_stack and heights[mono_stack[-1]]>=heights[i]:\n",
    "                mono_stack.pop(-1)\n",
    "            right[i] = mono_stack[-1] if mono_stack else n\n",
    "            mono_stack.append(i)\n",
    "        \n",
    "        maxArea = -float('inf')\n",
    "        for i in range(n):\n",
    "            areaTmp = (right[i]-left[i]-1)*heights[i]\n",
    "            maxArea = max(maxArea,areaTmp)\n",
    "        return maxArea\n",
    "\n",
    "\n",
    "if __name__=='__main__':\n",
    "    heights = [2,1,5,6,2,3]\n",
    "    solv = Solution()\n",
    "    print(solv.largestRectangleArea(heights))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "66cf98f8",
   "metadata": {},
   "outputs": [],
   "source": [
    "[85. 最大矩形 - 力扣（LeetCode）](https://leetcode.cn/problems/maximal-rectangle/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "b8ef3e69",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9\n"
     ]
    }
   ],
   "source": [
    "## 单调栈\n",
    "\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        # 把求最大矩形面积转换为四个求柱状最大面积问题，取最大\n",
    "        # 1 0 1 0 0        1 0 1 0 0\n",
    "        # 1 0 1 1 1   =》  2 0 2 1 1\n",
    "        # 1 1 1 1 1        3 1 3 2 2\n",
    "        # 1 0 0 1 0        4 0 0 3 0\n",
    "        #\n",
    "        #\n",
    "        matrix = list(map(lambda W: list(map(int,W)), matrix))\n",
    "        n,m = len(matrix),len(matrix[0])\n",
    "        state = [[0]*m for _ in range(n)]\n",
    "        # initial\n",
    "        for i in range(m):\n",
    "            state[0][i] = matrix[0][i]\n",
    "        for irow in range(1,n):\n",
    "            for icol in range(m):\n",
    "                if matrix[irow][icol]==0:\n",
    "                    state[irow][icol] = 0\n",
    "                else:\n",
    "                    state[irow][icol] = matrix[irow][icol]+state[irow-1][icol]\n",
    "        \n",
    "        # find the histogram Area\n",
    "        def maxHistArea(row:List[int])->int:\n",
    "            m = len(row)\n",
    "            left = [0]*m\n",
    "            right = [0]*m\n",
    "\n",
    "            # 利用单调栈，搜寻左边界\n",
    "            mono_stack = []\n",
    "            for i in range(m):\n",
    "                while mono_stack and row[mono_stack[-1]]>=row[i]:\n",
    "                    mono_stack.pop(-1)\n",
    "                left[i] = mono_stack[-1] if mono_stack else -1\n",
    "                mono_stack.append(i)\n",
    "            # 搜寻右边界\n",
    "            mono_stack = []\n",
    "            for i in range(m-1,-1,-1):\n",
    "                while mono_stack and row[mono_stack[-1]]>=row[i]:\n",
    "                    mono_stack.pop(-1)\n",
    "                right[i] = mono_stack[-1] if mono_stack else m\n",
    "                mono_stack.append(i)\n",
    "            # 计算每个高度的最大值，取最大的那个\n",
    "            maxArea = -float('inf')\n",
    "            for i in range(m):\n",
    "                tmp = (right[i]-left[i]-1)*row[i]\n",
    "                maxArea = max(maxArea,tmp)\n",
    "            return maxArea\n",
    "        \n",
    "        reMaxArea = -float('inf')\n",
    "        for i in range(n):\n",
    "            tmp = maxHistArea(state[i])\n",
    "            reMaxArea = max(reMaxArea,tmp)\n",
    "\n",
    "        return reMaxArea\n",
    "\n",
    "if __name__=='__main__':\n",
    "    matrix = [[\"0\",\"0\",\"1\",\"0\"],[\"0\",\"0\",\"1\",\"0\"],[\"0\",\"0\",\"1\",\"0\"],[\"0\",\"0\",\"1\",\"1\"],[\"0\",\"1\",\"1\",\"1\"],[\"0\",\"1\",\"1\",\"1\"],[\"1\",\"1\",\"1\",\"1\"]]\n",
    "    solv = Solution()\n",
    "    print(solv.maximalRectangle(matrix))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b13438b6",
   "metadata": {},
   "source": [
    "[86. 分隔链表 - 力扣（LeetCode）](https://leetcode.cn/problems/partition-list/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "6243ace3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 "
     ]
    }
   ],
   "source": [
    "## 链表的双向插入\n",
    "# 使用双指针分别指向出现目标值前的最后一个节点，和链表的尾部\n",
    "# 当两个指针相同的时候，更新前一个指针的时候也要更新后一个\n",
    "\n",
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "class Solution:\n",
    "    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:\n",
    "        h1 = ListNode(None)\n",
    "        reader = head\n",
    "\n",
    "\n",
    "        left,right = h1, h1\n",
    "        flag = False # 头指针标志位\n",
    "\n",
    "        while reader:\n",
    "            tmp = reader.next\n",
    "            if reader.val>=x: # 大于等于目标值，从尾部插入\n",
    "                reader.next = None\n",
    "                right.next = reader\n",
    "                right = right.next\n",
    "            else:\n",
    "                if left==right: # left和right相同时\n",
    "                    flag = True\n",
    "                reader.next = left.next # 否则从头部插入\n",
    "                left.next = reader\n",
    "                left = left.next\n",
    "                if flag: # left和right相同时，left更新后为了使得right指向最后，也要更新right指针指向最后一个\n",
    "                    right = right.next\n",
    "                    flag = False\n",
    "            reader = tmp\n",
    "        return h1.next\n",
    "\n",
    "if __name__=='__main__':\n",
    "    nums = [1,2,3]\n",
    "    x = 3\n",
    "    head = ListNode(None)\n",
    "    reader = head\n",
    "    for num in nums:\n",
    "        reader.next = ListNode(num)\n",
    "        reader = reader.next\n",
    "    head = head.next\n",
    "    solv = Solution()\n",
    "    newhead = solv.partition(head,x)\n",
    "    while newhead:\n",
    "        print(newhead.val,end=' ')\n",
    "        newhead = newhead.next\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93e3c4ae",
   "metadata": {},
   "source": [
    " [87. 扰乱字符串 - 力扣（LeetCode）](https://leetcode.cn/problems/scramble-string/)\n",
    "    \n",
    " \\***************\\*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "cff48da4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "## 动态规划   \n",
    "\n",
    "# coding=utf-8\n",
    "from typing import List\n",
    "from numpy import sort\n",
    "from functools import lru_cache\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def isScramble(self, s1: str, s2: str) -> bool:\n",
    "        @lru_cache\n",
    "        def dfs(i1: int, i2: int, length: int) -> bool:\n",
    "            \"\"\"\n",
    "            第一个字符串从 i1 开始，第二个字符串从 i2 开始，子串的长度为 length，是否和谐\n",
    "            \"\"\"\n",
    "\n",
    "            # 判断两个子串是否相等\n",
    "            if s1[i1:i1+length] == s2[i2:i2+length]:\n",
    "                return True\n",
    "            \n",
    "            # 判断是否存在字符 c 在两个子串中出现的次数不同\n",
    "            if Counter(s1[i1:i1+length]) != Counter(s2[i2:i2+length]):\n",
    "                return False\n",
    "            \n",
    "            # 枚举分割位置\n",
    "            for i in range(1, length):\n",
    "                # 不交换的情况\n",
    "                if dfs(i1, i2, i) and dfs(i1 + i, i2 + i, length - i):\n",
    "                    return True\n",
    "                # 交换的情况\n",
    "                if dfs(i1, i2 + length - i, i) and dfs(i1 + i, i2, length - i):\n",
    "                    return True\n",
    "        \n",
    "            return False\n",
    "\n",
    "        ans = dfs(0, 0, len(s1))\n",
    "        dfs.cache_clear()\n",
    "        return ans\n",
    "\n",
    "if __name__=='__main__':\n",
    "    s1 = \"abcde\"\n",
    "    s2 = \"caebd\"\n",
    "    solv = Solution()\n",
    "    print(solv.isScramble(s1,s2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cdf4848d",
   "metadata": {},
   "source": [
    "[88. 合并两个有序数组 - 力扣（LeetCode）](https://leetcode.cn/problems/merge-sorted-array/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "8463bd5e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 2, 3, 5, 6]\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums1 in-place instead.\n",
    "        \"\"\"\n",
    "        ## 归并排序\n",
    "        Lst1 = []\n",
    "        Lst2 = []\n",
    "        for i in range(m):\n",
    "            Lst1.append(nums1[i])\n",
    "        Lst1.append(float('inf'))\n",
    "\n",
    "        for i in range(n):\n",
    "            Lst2.append(nums2[i])\n",
    "        Lst2.append(float('inf'))\n",
    "\n",
    "        pos = 0\n",
    "        i=j=0\n",
    "        while pos<m+n:\n",
    "            if Lst1[i]<=Lst2[j]:\n",
    "                nums1[pos] = Lst1[i]\n",
    "                i+=1\n",
    "            else:\n",
    "                nums1[pos] = Lst2[j]\n",
    "                j+=1\n",
    "            pos += 1\n",
    "\n",
    "if __name__=='__main__':\n",
    "    nums1 = [1,2,3,0,0,0]\n",
    "    nums2 = [2,5,6]\n",
    "    m,n = 3,3\n",
    "    solv = Solution()\n",
    "    solv.merge(nums1,m,nums2,n)\n",
    "    print(nums1)\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3d9ffe6",
   "metadata": {},
   "source": [
    "[89. 格雷编码 - 力扣（LeetCode）](https://leetcode.cn/problems/gray-code/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9939dd7a",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def grayCode(self, n: int) -> List[int]:\n",
    "        # 格雷码的生成过程\n",
    "        # i^(i>>1)\n",
    "        # n=3\n",
    "        # 000\n",
    "        # 1^(1>>1)=> 001^000 = 001\n",
    "        # 2^(2>>1)=> 010^001 = 011\n",
    "        # 3^(3>>1)=> 011^001 = 010\n",
    "        # ...\n",
    "        # 7^(7>>1)=> 111^011 = 100\n",
    "        res = [0]\n",
    "        for i in range(1,n):\n",
    "            res.append(i^(i>>1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66c56be6",
   "metadata": {},
   "source": [
    "[90. 子集 II - 力扣（LeetCode）](https://leetcode.cn/problems/subsets-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "ab561dd2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[], [1, 2, 2], [1, 2], [1], [2, 2], [2]]\n"
     ]
    }
   ],
   "source": [
    "## 回溯方法\n",
    "# 因为不能用重复子集，所以需要对固定含有相同元素的list的元素顺序\n",
    "\n",
    "# coding=utf-8\n",
    "from copy import deepcopy\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        ## 回溯\n",
    "\n",
    "        res = [[]]\n",
    "        def backTrack(pos:int,Lst:List[int])->None:\n",
    "            nonlocal res, nums\n",
    "            if pos>=len(nums):\n",
    "                return\n",
    "\n",
    "            Lst.append(nums[pos])\n",
    "            backTrack(pos+1,Lst)\n",
    "\n",
    "            Lst1 = sorted(Lst) # 固定插入Lst的顺序\n",
    "            if Lst1 not in res:\n",
    "                res.append(deepcopy(Lst1))\n",
    "                \n",
    "            Lst.pop(-1)\n",
    "            backTrack(pos+1,Lst)\n",
    "\n",
    "        backTrack(0,[])\n",
    "        return res\n",
    "\n",
    "if __name__=='__main__':\n",
    "    nums = [1,2,2]\n",
    "    solv = Solution()\n",
    "    print(solv.subsetsWithDup(nums))\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99be3fe5",
   "metadata": {},
   "source": [
    "[91. 解码方法 - 力扣（LeetCode）](https://leetcode.cn/problems/decode-ways/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "c7671488",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "## 动态规划\n",
    "\n",
    "# coding=utf-8\n",
    "from tkinter import N\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        ## 动态规划\n",
    "        # 定义状态：dp[i] 表示状态解码s[:i+1]的解码数 \n",
    "        # dp[i] 有两种动作，\n",
    "            # 1. 上一次解码使用了一个字符，s[i],要求s[i]!=0, \n",
    "            # 这种方案的解码数=dp[i]\n",
    "            # 2. 上一次使用了两个字符，s[i-1:i+1],\n",
    "            # 要求s[i-1]!=0 and int(s[i-1:i+1])<=26, 此时解码数为dp[i-2]\n",
    "        dp = [0]*len(s)\n",
    "\n",
    "        if s[0]=='0':\n",
    "            return 0\n",
    "        dp[0] = 1\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i]!='0':\n",
    "                dp[i]+= dp[i-1]\n",
    "            if s[i-1]!='0' and int(s[i-1:i+1])<=26:\n",
    "                if i==1:\n",
    "                    dp[i]+=1\n",
    "                else: \n",
    "                    dp[i]+=dp[i-2]\n",
    "        return dp[-1]\n",
    "\n",
    "if __name__=='__main__':\n",
    "    s = '10'\n",
    "    solv = Solution()\n",
    "    print(solv.numDecodings(s))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7a0d254e",
   "metadata": {},
   "source": [
    "[92. 反转链表 II - 力扣（LeetCode）](https://leetcode.cn/problems/reverse-linked-list-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "5cb5e60e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 3 2 8 4 5 "
     ]
    }
   ],
   "source": [
    "## 链表翻转\n",
    "# 先把目标段从原链表中删除，以前插的方式加入新链表（翻转）\n",
    "# 找到插入点，把翻转后的目标段加入到目标\n",
    "\n",
    "# coding=utf-8\n",
    "from email import header\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "class Solution:\n",
    "    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:\n",
    "        ##\n",
    "        h1 = ListNode(None)\n",
    "        pos = h1\n",
    "\n",
    "        # 计算长度\n",
    "        reader = head\n",
    "        length = 0\n",
    "        while reader:\n",
    "            length +=1\n",
    "            reader = reader.next\n",
    "        if length == 1:\n",
    "            return head\n",
    "\n",
    "        h0 = ListNode(None)\n",
    "        h0.next = head\n",
    "        reader= h0\n",
    "        count = 1\n",
    "        # 把目标段从原链表删除，并以前插的方式加入新链表（翻转）\n",
    "        while count<=right:\n",
    "            if left<=count<=right: \n",
    "                tmp = reader.next\n",
    "                # 删除\n",
    "                if reader==h0:\n",
    "                    reader.next = reader.next.next\n",
    "                    h0 = reader # 跟新头\n",
    "                else:\n",
    "                    reader.next = reader.next.next # 删除\n",
    "                # 前插入新列表\n",
    "                tmp.next = pos.next\n",
    "                pos.next = tmp\n",
    "                count += 1\n",
    "                continue\n",
    "            count+=1\n",
    "            reader = reader.next\n",
    "\n",
    "        # 把翻转后的链表插入原链表\n",
    "        reader = h0\n",
    "        count = 1\n",
    "        while count<left: # 找到插入节点 left\n",
    "            count+=1\n",
    "            reader = reader.next\n",
    "        # 插入\n",
    "        pos = h1.next\n",
    "        while pos:\n",
    "            tmp = pos.next\n",
    "            pos.next = reader.next\n",
    "            reader.next = pos\n",
    "            reader = reader.next\n",
    "            pos = tmp\n",
    "    \n",
    "        return h0.next\n",
    "     \n",
    "\n",
    "\n",
    "if __name__=='__main__':\n",
    "    nums = [1,8,2,3,4,5]\n",
    "    left,right = 2,4\n",
    "    head = ListNode(None)\n",
    "    reader = head\n",
    "    for num in nums:\n",
    "        reader.next = ListNode(num)\n",
    "        reader = reader.next\n",
    "    head = head.next\n",
    "    solv = Solution()\n",
    "    newhead = solv.reverseBetween(head,left,right)\n",
    "    while newhead:\n",
    "        print(newhead.val, end=' ')\n",
    "        newhead = newhead.next\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5e1c9ca",
   "metadata": {},
   "source": [
    "[93. 复原 IP 地址 - 力扣（LeetCode）](https://leetcode.cn/problems/restore-ip-addresses/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "183bf016",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['0.10.0.10', '0.100.1.0']\n"
     ]
    }
   ],
   "source": [
    "## 回溯算法\n",
    "\n",
    "# coding=utf-8\n",
    "from copy import deepcopy\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        if len(s)<4 or len(s)>12:\n",
    "            return res\n",
    "        ## 使用回溯算法，找到所有位点的插入方法,然后对每一种方式进行检查，\n",
    "        sites = list(range(1,len(s)))\n",
    "        stack = []\n",
    "        def backTrack(Lst:List[int],pos:int)->None:  \n",
    "            if len(Lst)>=3:\n",
    "                if Lst not in stack:\n",
    "                    stack.append(deepcopy(Lst))\n",
    "                return\n",
    "\n",
    "            nonlocal sites \n",
    "            if pos>=len(sites):\n",
    "                return\n",
    "\n",
    "            Lst.append(sites[pos])\n",
    "            backTrack(Lst,pos+1)\n",
    "            Lst.pop(-1)\n",
    "            backTrack(Lst,pos+1)\n",
    "\n",
    "\n",
    "        backTrack([],0)\n",
    "        # check\n",
    "        for ip in stack:\n",
    "            tmps = [s[0:ip[0]],s[ip[0]:ip[1]],s[ip[1]:ip[2]],s[ip[2]:len(s)]]\n",
    "            flag = True\n",
    "            for tmp in tmps:\n",
    "                if (tmp[0]=='0' and len(tmp)>1) or int(tmp)>255:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                res.append('.'.join(tmps))       \n",
    "        return res\n",
    "\n",
    "if __name__=='__main__':\n",
    "    s = \"010010\"\n",
    "    solv = Solution()\n",
    "    print(solv.restoreIpAddresses(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04ae6a68",
   "metadata": {},
   "source": [
    "[94. 二叉树的中序遍历 - 力扣（LeetCode）](https://leetcode.cn/problems/binary-tree-inorder-traversal/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "7bc50c9c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 4, 5, 3, 6]\n",
      "[4, 2, 5, 1, 6, 3]\n",
      "[4, 5, 2, 6, 3, 1]\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "## 二叉树的遍历\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "# 前序遍历\n",
    "res_pre_order = []\n",
    "def pre_order(BT:TreeNode)->None:\n",
    "    if BT:\n",
    "        res_pre_order.append(BT.val)\n",
    "        pre_order(BT.left)\n",
    "        pre_order(BT.right)\n",
    "\n",
    "# 中序遍历\n",
    "res_in_order = []\n",
    "def in_order(BT:TreeNode)->None:\n",
    "    if BT:\n",
    "        in_order(BT.left)\n",
    "        res_in_order.append(BT.val)\n",
    "        in_order(BT.right)\n",
    "\n",
    "# 后序遍历\n",
    "res_tail_order = []\n",
    "def tail_order(BT:TreeNode)->None:\n",
    "    if BT:\n",
    "        tail_order(BT.left)\n",
    "        tail_order(BT.right)\n",
    "        res_tail_order.append(BT.val)\n",
    "\n",
    "if __name__=='__main__':\n",
    "    # 新建二叉树\n",
    "    # 特性： 节点i的两个子节点分别为i*2, i*2+1\n",
    "    lst = [1,2,3,4,5,6]\n",
    "    \n",
    "    lst.insert(0,0)\n",
    "    n = len(lst)\n",
    "\n",
    "    # 新建二叉树\n",
    "    def creatBT(newLst:List[int],pos:int)->TreeNode:\n",
    "        if pos>=len(newLst):\n",
    "            return None\n",
    "        root = TreeNode(newLst[pos],None,None)\n",
    "        root.left = creatBT(newLst,pos*2)\n",
    "        root.right = creatBT(newLst,pos*2+1)\n",
    "        return root\n",
    "    \n",
    "    root = creatBT(lst,1)\n",
    "\n",
    "    pre_order(root)\n",
    "    print(res_pre_order)\n",
    "    in_order(root)\n",
    "    print(res_in_order)\n",
    "    tail_order(root)\n",
    "    print(res_tail_order)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f2dfe7e2",
   "metadata": {},
   "source": [
    "[95. 不同的二叉搜索树 II - 力扣（LeetCode）](https://leetcode.cn/problems/unique-binary-search-trees-ii/)\n",
    "\n",
    "\\*************************\\*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "63c88c84",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from __future__ import all_feature_names\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    ## 使用回溯方法遍历所有可能\n",
    "    # 分别以每一个顶点作为根节点构建二叉搜索树\n",
    "    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:\n",
    "        def generateTrees(start:int,end:int)->List[Optional[TreeNode]]:\n",
    "            if start>end:\n",
    "                return [None]\n",
    "            \n",
    "            allTrees = []\n",
    "            for i in range(start,end+1):\n",
    "                leftNodes = generateTrees(start,i-1)\n",
    "                rightNodes = generateTrees(i+1,end)\n",
    "\n",
    "                for l in leftNodes:\n",
    "                    for r in rightNodes:\n",
    "                        TN = TreeNode(i,None,None)\n",
    "                        TN.left = l\n",
    "                        TN.right = r\n",
    "                        allTrees.append(TN)\n",
    "            return allTrees\n",
    "        \n",
    "        return generateTrees(1,n)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e79dbf55",
   "metadata": {},
   "source": [
    "[96. 不同的二叉搜索树 - 力扣（LeetCode）](https://leetcode.cn/problems/unique-binary-search-trees/) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "c100310d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def numTrees(self, n: int) -> int:\n",
    "        ## 动态规划问题\n",
    "        # G(n) 表示长度为n的序列对于的二叉搜索树的个数\n",
    "        # F(j,m) 表示以i为根节点，m为序列长度的搜索数个数\n",
    "        # G(i)  = \\sum_{1<=j<=i} F(j,i)\n",
    "        # F(j,i) = G(j-1)*G(i-j)\n",
    "        # G(i) = \\sum_{1<=j<=i} {G(j-1)*G(i-j)}\n",
    "        G = [0]*(n+1)\n",
    "        G[0],G[1] = 1, 1\n",
    "\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(1,i+1):\n",
    "                G[i] += G[j-1]*G[i-j]\n",
    "\n",
    "        return G[n]\n",
    "\n",
    "if __name__=='__main__':\n",
    "    n = 3\n",
    "    solv = Solution()\n",
    "    print(solv.numTrees(n))\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0ba182e8",
   "metadata": {},
   "source": [
    "[97. 交错字符串 - 力扣（LeetCode）](https://leetcode.cn/problems/interleaving-string/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "bbfdcdc3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "\n",
    "        ## 使用动态规范解题\n",
    "        # 定义f(i,j),表示s1前i个字符和s2的前j的字符是否可以组成s3，True or False\n",
    "        # 分为以s1结尾和s2结尾，\n",
    "        # s1结尾：\n",
    "        #   s1的第i个字符（s[i-1]）与s3的第i+j的字符(s[i+j-1])相同\n",
    "        # s2结尾：\n",
    "        #   s2的第j个字符（s[j-1]) 与s3的第i+j的字符（s[i+j-1])相同\n",
    "        # f(i,j) = (f(i-1,j) and s1[i-1]==s3[i+j-1]) or (f(i,j-1) and s2[j-1]==s3[i+j-1])\n",
    "        n1,n2,n3 = len(s1),len(s2),len(s3)\n",
    "        if n1+n2!=n3:\n",
    "            return False\n",
    "\n",
    "        dp = [[False]*(n2+1) for _ in range(n1+1)]\n",
    "        dp[0][0] = True\n",
    "        for i2 in range(1,n2+1):\n",
    "            dp[0][i2] = (s2[i2-1]==s3[i2-1]) and (dp[0][i2-1])\n",
    "        for i1 in range(1,n1+1):\n",
    "            dp[i1][0] = (s1[i1-1]==s3[i1-1]) and (dp[i1-1][0])\n",
    "        for i1 in range(1,n1+1):\n",
    "            for i2 in range(1,n2+1):\n",
    "                dp[i1][i2] = (s1[i1-1]==s3[i1+i2-1] and dp[i1-1][i2]) \\\n",
    "                    or (s2[i2-1]==s3[i1+i2-1] and dp[i1][i2-1])\n",
    "        return dp[n1][n2]\n",
    "\n",
    "\n",
    "\n",
    "if __name__=='__main__':\n",
    "    s1 = 'aabcc'\n",
    "    s2 = 'dbbca'\n",
    "    s3 = 'aadbbcbcac'\n",
    "    solv = Solution()\n",
    "    print(solv.isInterleave(s1,s2,s3))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "798207b0",
   "metadata": {},
   "source": [
    "[98. 验证二叉搜索树 - 力扣（LeetCode）](https://leetcode.cn/problems/validate-binary-search-tree/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1ec5f3f1",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 二叉搜索树中序遍历后为升序\n",
    "\n",
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isValidBST(self, root: Optional[TreeNode]) -> bool:\n",
    "        res = []\n",
    "        def in_order(root:TreeNode)->None:\n",
    "            if root:\n",
    "                nonlocal res\n",
    "                in_order(root.left)\n",
    "                res.append(root.val)\n",
    "                in_order(root.right)\n",
    "        \n",
    "        in_order(root)\n",
    "\n",
    "        flag = True\n",
    "        for i in range(len(res)-1):\n",
    "            if res[i]>=res[i+1]:\n",
    "                flag = False\n",
    "                break\n",
    "        return True if flag else False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15f4f931",
   "metadata": {},
   "source": [
    "[99. 恢复二叉搜索树 - 力扣（LeetCode）](https://leetcode.cn/problems/recover-binary-search-tree/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e2d1a863",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 中序遍历找到异常对\n",
    "## 在只有一对数据异常的升序序列中，定位这对数据：找到两个降序对，第一对的首个，和第二对的后一个\n",
    "\n",
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def recoverTree(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        ## 中序遍历二叉搜索树，找到错误节点，交换两个节点的值\n",
    "        nodes = []\n",
    "        reader = root\n",
    "        def in_order(root:TreeNode)->None:\n",
    "            nonlocal nodes\n",
    "            if root:\n",
    "                in_order(root.left)\n",
    "                nodes.append(root)\n",
    "                in_order(root.right)\n",
    "\n",
    "        in_order(root)\n",
    "        pre,x,y = 0,0,0\n",
    "        flag = True\n",
    "        for i in range(1,len(nodes)):\n",
    "            if nodes[pre].val>nodes[i].val:\n",
    "                if flag:\n",
    "                    x = pre\n",
    "                    flag = False\n",
    "                y = i\n",
    "            pre = i\n",
    "        nodes[x].val,nodes[y].val  = nodes[y].val, nodes[x].val\n",
    "                "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "393f1e87",
   "metadata": {},
   "source": [
    "[100. 相同的树 - 力扣（LeetCode）](https://leetcode.cn/problems/same-tree/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "35a06761",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:\n",
    "        ## 深度优先遍历,递归判定左右节点\n",
    "\n",
    "        # 边界\n",
    "        if p and not q:\n",
    "            return False\n",
    "        if not p and q:\n",
    "            return False\n",
    "        if not p and not q:\n",
    "            return True\n",
    "        if p.val != q.val:\n",
    "            return False\n",
    "        else:\n",
    "            return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
